package 中等.分治;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，
 * 计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
 * 生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/different-ways-to-add-parentheses
 */
public class 为运算表达式设计优先级_241 {

    public static void main(String[] args) {

        System.out.println(new 为运算表达式设计优先级_241().diffWaysToCompute("2*3-4*5"));

    }

    /**
     * 对于 x op y ，可以将 x 的个数，和 y 的个数求出来
     * 根据乘法原理，可以让 x1 op y1 ，x1 op y2 ...
     * 得出 x op y 的答案
     * <p>
     * 对于 x 和 y 可以是一个复杂的运算，可以采用递归
     * 直到 x 和 y 中不存在任何运算符，递归停止
     */
    public List<Integer> diffWaysToCompute(String expression) {
        return dfs(0, expression.length() - 1, expression.toCharArray());
    }

    private List<Integer> dfs(int left, int right, char[] chars) {
        List<Integer> list = new ArrayList<>();

        for (int i = left; i <= right; i++) {
            if (!Character.isDigit(chars[i])) {
                List<Integer> l1 = dfs(left, i - 1, chars);
                List<Integer> l2 = dfs(i + 1, right, chars);
                for (Integer n1 : l1) {
                    for (Integer n2 : l2) {
                        if ('+' == chars[i]) {
                            list.add(n1 + n2);
                        } else if ('-' == chars[i]) {
                            list.add(n1 - n2);
                        } else {
                            list.add(n1 * n2);
                        }
                    }
                }
            }
        }

        // 为空说明[left,right]没有任何运算符
        if (list.isEmpty()) {
            int n = 0;
            int num = 0;
            for (int i = right; i >= left; i--) {
                num += (chars[i] - '0') * Math.pow(10, n);
                n++;
            }
            list.add(num);
        }
        return list;
    }

}
